题目

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

解答

二维动态规划

定义状态

dp[i][j] 表示 s 的前 i个字符与 p 中的前 j 个字符是否能够匹配。

初始状态：

  • dp[0][0] = 1，都是空串可以匹配成功
  • s 是空串时，p若不为空必须用 * 抵消前一个字符

状态转移方程

注意字符串索引对应dp矩阵索引-1。

  • 当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
  1. dp[i][j - 2]： 即将字符组合 p[j - 2]* 看作出现 0 次时，能否匹配；
  2. dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
  3. dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配；
  • 当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
  1. dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
  2. dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 '.' 看作字符 s[i - 1] 时，能否匹配；

最终答案：dp[m][n]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool isMatch(char a, char b) {
        return a == b || b == '.';
    }

    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<int>> dp(m+1 ,vector<int>(n+1, 0)); // dp[i][j] 表示s[0..i-1]和p[0...j-1]是否匹配
        // 基本状态初始化
        dp[0][0] = 1; // p, s都是空串
        for (int j=1; j<=n; ++j) { // s是空串，p可以用*抵消前一个字符
            if (p[j-1] == '*') {
                dp[0][j] = dp[0][j-2];
            }
        }
        // 状态转移
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                if (isMatch(s[i-1], p[j-1])) { // 当前字符match，抵消
                    dp[i][j] = dp[i-1][j-1];
                }else if (p[j-1] == '*') { // 若不match，可以借助*抵消 
                    if (j > 1) {
                        if (isMatch(s[i-1], p[j-2])) { // s中前一个字符与p当前字符match
                            // 1. 匹配0次 ，即忽略 p[j-2],p[j-1] 这两个字符，s[0...i-1]与p[0...j-3]匹配
                            // 2. 匹配>=1次，即忽略 s[i-1] 这个字符，s[0...i-2]与p[0...j-1]匹配
                            dp[i][j] = dp[i][j-2] | dp[i-1][j];
                        } else { // s中前一个字符与p当前字符match
                            // 必须用*消去p[j-2]，则s[0...i-1]与p[0...j-3]匹配
                            dp[i][j] = dp[i][j-2];
                        }
                    }
                }
            }
        }
        return dp[m][n] == 1;
    }
};

复杂度

  • 时间复杂度 $O(m*n)$
  • 空间复杂度 $O(m*n)$